package Leetcode;

// import java.util.List;

class Solution_148_1 {
    // 自底向上的归并排序
    public ListNode sortList(ListNode head) {
        // 剪枝
        if (head == null)
            return head;

        // 获取链表长度
        int length = 0;
        ListNode node = head;
        while (node != null) {
            length++;
            node = node.next;
        }

        ListNode prehead = new ListNode(0, head);
        // 字串长度逐渐翻倍
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            ListNode prev = prehead;
            ListNode curr = prehead.next;

            while (curr != null) {
                // 第一个子表的头结点
                ListNode head1 = curr;
                for (int i = 1; i < subLength && curr.next != null; i++)
                    curr = curr.next;

                // 第二个子表的头结点
                ListNode head2 = curr.next;
                // 断开第一个子表
                curr.next = null;
                curr = head2;
                for (int i = 1; i < subLength && curr != null && curr.next != null; i++)
                    curr = curr.next;

                ListNode next = null; // 记录下一个子表的起始位置
                if (curr != null) { // 如果没有到头则断开第二个子表
                    next = curr.next;
                    curr.next = null;
                }
                curr = next;

                // 合并链表添加到最终节点pre中
                ListNode merged = merge(head1, head2);
                prev.next = merged;
                while (prev.next != null) // 此处绝对不要写成prev!=null，否则再下一次遍历时pre=null没有next指针
                    prev = prev.next;
            }
        }
        return prehead.next;
    }

    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode prehead = new ListNode(0);
        ListNode temp = prehead;
        ListNode temp1 = head1;
        ListNode temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null)
            temp.next = temp1;
        else if (temp2 != null)
            temp.next = temp2;
        return prehead.next;
    }
}

class Solution_148_2 {
    // 自顶向下的归并排序
    public ListNode sortList(ListNode head) {
        return mergeSort(head, null);
    }

    public ListNode mergeSort(ListNode head, ListNode tail) {
        // 剪枝
        if (head == null)
            return head;
        // 如果长度为1，将单个节点分割出来
        if (head.next == tail) {
            head.next = null;
            return head;
        }

        // 只用快慢指针找到中间位置
        ListNode slow = head;
        ListNode fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail)
                fast = fast.next;
        }

        ListNode list1 = mergeSort(head, slow); // 包括head不包括slow
        ListNode list2 = mergeSort(slow, tail);
        return merge(list1, list2);

    }

    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode prehead = new ListNode(0);
        ListNode temp = prehead;
        ListNode temp1 = head1;
        ListNode temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null)
            temp.next = temp1;
        else if (temp2 != null)
            temp.next = temp2;
        return prehead.next;
    }
}